/*
 *https://leetcode.cn/problems/house-robber/
 *198. 打家劫舍
 *medium, 吴朝泽 2024.9.2
 *动态规划
dp数组为偷取的金额，重点算法为每个房间有偷和不偷两种状态，偷窃第 k 间房屋，
那么就不能偷窃第 k−1 间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 k 间房屋的金额之和。
如果不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。
在两个选项中选择偷窃总金额较大的选项，该选项对应的偷窃总金额即为前 k 间房屋能偷窃到的最高总金额。
*/

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        int dp[1000];
        if(n == 1)
            return nums[0];
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);
        for(int i = 2; i < n; i++)
        {
            dp[i] = max(dp[i-1],nums[i] + dp[i-2]);
        }
        return dp[n-1];
    }
};